package string;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。
 * 当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：
 * 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
 * 请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。
 * <p>
 * 示例 1：
 * 输入：s = "aaba*"
 * 输出："aab"
 * 解释：
 * 删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。
 * <p>
 * 示例 2：
 * 输入：s = "abc"
 * 输出："abc"
 * 解释：
 * 字符串中没有 '*' 字符。
 *
 * @author Jisheng Huang
 * @version 20250607
 */
public class ClearStars_3170 {
    public static String clearStars(String s) {
        Deque<Integer>[] cnt = new Deque[26];

        // Initialize the deque array for 26 characters
        for (int i = 0; i < 26; ++i) {
            cnt[i] = new ArrayDeque<>();
        }

        char[] arr = s.toCharArray();

        // Loop through the character array
        for (int i = 0; i < s.length(); ++i) {
            // If the current character is not *, push to the corresponding deque
            // If it is *, make the smallest character as *
            if (arr[i] != '*') {
                cnt[arr[i] - 'a'].push(i);
            } else {
                for (int j = 0; j < 26; ++j) {
                    if (!cnt[j].isEmpty()) {
                        arr[cnt[j].pop()] = '*';
                        break;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        // Loop through the array, if the current character it not *, push to the StringBuilder
        for (char c : arr) {
            if (c != '*') {
                sb.append(c);
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        String s = "aaba*";
        System.out.println(clearStars(s));

        s = "abc";
        System.out.println(clearStars(s));
    }
}
